package structural_pattern.adapter_pattern;

/**
 * 适配者 快速排序
 */
public class QuickSort {
  public int[] quickSort(int array[]){
      sort(array,0,array.length-1);
      return array;

  }

    private void sort(int[] array, int p, int r) {
      int q = 0;
      if(p<r){
          q = partion(array,p,r);
          sort(array,p,q-1);
          sort(array,q+1,r);
      }
  }

    private int partion(int[] array, int p, int r) {
      int x = array[r];
      int j = p-1;
        for (int i = p; i <= r-1; i++) {
            if (array[i]<=x){
                j++;
                swap(array,j,i);
            }
        }
        swap(array,j+1,r);
      return j+1;
    }

    private void swap(int[] array, int i, int r) {
      int t = array[i];
      array[i] = array[r];
      array[r] = t;
    }
}
